对个元素采用简单选择排序，比较次数和移动次数分别为：
对于10个数的简单选择排序，最坏情况下需要交换元素的次数为：
对大部分元素已有序的数组进行排序时，直接插入排序比简单选择排序效率更高，其原因是：
设有100个元素的有序序列，如果用二分插入排序再插入一个元素，则最大比较次数是：
对一组包含10个元素的非递减有序序列，采用直接插入排序排成非递增序列，其可能的比较次数和移动次数分别是：
设有1000个元素的有序序列，如果用二分插入排序再插入一个元素，则最大比较次数是：
有组记录的排序码为{ 46，79，56，38，40，84 }，则利用堆排序的方法建立的初始堆为：
对个记录进行堆排序，最坏的情况下时间复杂度是：
对个记录进行堆排序，需要的额外空间为：
对个不同的数据采用冒泡算法进行从大到小的排序，下面哪种情况下肯定交换元素次数最多？
对于7个数进行冒泡排序，需要进行的比较次数为：
对于序列{ 49，38，65，97，76，13，27，50 }，按由小到大进行排序，下面哪一个是初始步长为4的希尔排序法第一趟的结果？
给定初始待排序列{ 15，9，7，8，20，-1，4 }。如果希尔排序第一趟结束后得到序列为{ 15，-1，4，8，20，9，7 }，则该趟增量为：
对初始数据序列{ 8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 }进行希尔排序。若第一趟排序结果为（ 1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8 ），第二趟排序结果为（ 1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9 ），则两趟排序采用的增量（间隔）依次是：
采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是：
对个记录进行快速排序，在最坏的情况下，其时间复杂度是：
有组记录的排序码为{46，79，56，38，40，84 }，采用快速排序（以位于最左位置的对象为基准而）得到的第一次划分结果为：
在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左右指针都会停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？
在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左右指针都不停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？
在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左指针停止移动，而右指针在同样情况下却不停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？
对个记录进行归并排序，归并趟数的数量级是：
桶排序算法的时间复杂度T(M, N)是多少？
void Bucket_Sort(ElementType A[], int N)
{ count[]初始化;
while (读入1个学生成绩grade)
将该生插入count[grade]链表;
for ( i=0; i<M; i++ ) {
if ( count[i] )
输出整个count[i]链表;
}
}
给出关键字序列{ 321，156，57，46，28，7，331，33，34，63 }，下面哪个选择是按次位优先（LSD）链式基数排序进行了一趟分配和收集的结果？
对给定序列{ 110，119，7，911，114，120，122 }采用次位优先（LSD）的基数排序，则两趟收集后的结果为：
给出关键字序列{ 431, 56, 57, 46, 28, 7, 331, 33, 24, 63 }，下面哪个选择是按次位优先（LSD）链式基数排序进行了一趟分配和收集的结果？
给出关键字序列{ 4321, 56, 57, 46, 28, 7, 331, 33, 234, 63 }，下面哪个选择是按次位优先（LSD）链式基数排序进行了一趟分配和收集的结果？
给出关键字序列{ 4321, 56, 57, 46, 289, 17, 331, 33, 234, 63 }，下面哪个选择是按次位优先（LSD）链式基数排序进行了一趟分配和收集的结果？
设数组 S[ ]={93, 946, 372, 9, 146, 151, 301, 485, 236, 327, 43, 892}，采用最低位优先（LSD）基数排序将 S 排列成升序序列。第 1 趟分配、收集后，元素 372 之前、之后紧邻的元素分别是：
给定A[]={46, 23, 8, 99, 31, 12, 85}，调用非递归的归并排序加表排序执行第1趟后，表元素的结果是：
对于外排序中的 路归并， 不取很大值的首要原因是：
设我们的内存可以一次处理 12 个数字，且磁带上有以下两条有序段：
有序段1: 1, 3, 5, 7, 8, 9, 10, 12
有序段2: 2, 4, 6, 15, 20, 25, 30, 32
采用2路归并，并设置4块输入缓冲区和2块输出缓冲区，以便并行操作。则下列哪三个操作是不能并行的？
在外排序中，为了减少归并的趟数，最小化初始归并段的个数（即产生更长的有序段）是个不错的主意。设输入的键值为 (25, 74, 56, 34, 21, 11, 29, 80, 38, 53)，且内存仅够处理 3 个记录，则用替换选择法产生的初始段的最小个数为__。
下列排序算法中，哪种算法可能出现：在最后一趟开始之前，所有的元素都不在其最终的位置上？（设待排元素个数）
若数据元素序列{ 11，12，13，7，8，9，23，4，5 }是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是：
数据序列{ 3，2，4，9，8，11，6，20 }只能是下列哪种排序算法的两趟排序结果？
就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是：
下面四种排序算法中，稳定的算法是：
输入个只有一位数字的整数，可以用复杂度将其排序的算法是：
对10TB的数据文件进行排序，应使用的方法是：
假设我们只有2条磁带和用于做外部排序。假设内存可以一次处理条记录。初始状态下上存有条记录。下列简单算法的执行步骤为：
重复第2、3步，直到全部记录有序。上述算法需要执行__轮。
给出关键字序列{ 321，156，57，46，28，7，331，33，34，63 }，按次位优先（LSD）链式基数排序进行两趟分配和收集的结果为：
参考下列的写法：
对给定序列{ 110，119，7，911，114，120，122 }按次位优先（LSD）链式基数排序进行两趟分配和收集的结果为：
→110→120→911→122→114→7→119
本题要求用冒泡排序将一组整数按增序排序。冒泡排序每次从头到尾扫描待排序列，检查相邻两数的顺序，如果顺序不对就交换。请补全下列冒泡排序的代码。
typedef struct node *nodeptr;
struct node{
int value;
nodeptr next;
/* 一些其他的项，在此忽略 */
};
nodeptr BubbleSort (nodeptr h)
{/* h 是带空头结点的链表的头指针 */
nodeptr p, q;
int flag_swap;
if (!h->next) return h;
do{
flag_swap = 0;
p = h;
while (p->next->next){
if ( 1分 ){
flag_swap++;
q = p->next;
1分;
1分;
1分;
}
else p = p->next;
}
} while (flag_swap > 0);
return h;
}
下列代码的功能是利用堆排序将N个元素按非递减顺序排序。
#define leftchild(i) ( 2*(i)+1 )
void PercDown( ElementType A[], int i, int N )
{ int child;
ElementType Tmp;
for ( Tmp = A[i]; leftchild(i) < N; i = child ) {
child = leftchild(i);
if (1分)
child ++;
if (1分) A[i] = A[child];
else break;
}
1分;
}
void Heapsort( ElementType A[ ], int N )
{ int i;
for ( i = N / 2; i>= 0; i -- ) /* BuildHeap */
PercDown( A, i, N );
for ( i = N-1; i >0; i -- ) {
Swap( &A[ 0 ], &A[ i ] );
1分;
}
}
下列代码的功能是将一列元素{ r[1] … r[n] }按其键值 key 的非递减顺序排序。普通选择排序是每次仅将一个待排序列的最小元放到正确的位置上，而这个另类的选择排序是每次从待排序列中同时找到最小元和最大元，把它们放到最终的正确位置上。
void sort( list r[], int n )
{
int i, j, mini, maxi;
for (i=1; i<n-i+1; i++) {
mini = maxi = i;
for( j=i+1; 1分; ++j ){
if( 1分 ) mini = j;
else if(r[j]->key > r[maxi]->key) maxi = j;
}
if( 1分 ) swap(&r[mini], &r[i]);
if( maxi != n-i+1 ){
if( 1分 ) swap(&r[mini], &r[n-i+1]);
else swap(&r[maxi], &r[n-i+1]);
}
}
}
本题要求给出希尔排序对给定初始序列{9, 8, 7, 6, 5, 4, 3, 2, 1}利用增量序列{1, 3, 7}进行排序的分步结果。将每步结果填在下列空中。注意：相邻数字间必须有一个空格，开头结尾不得有多余空格。
| 原始序列 | 9 8 7 6 5 4 3 2 1 |
|---|---|
| 增量7排序后 | 2分 |
| 增量3排序后 | 2分 |
| 增量1排序后 | 1 2 3 4 5 6 7 8 9 |
归并排序。
#include <iostream>
#define MAXSIZE 1000
using namespace std;
typedef struct
{
int key;
char *otherinfo;
}RedType;
typedef struct
{
RedType *r;
int length;
}SqList;
void Create_Sq(SqList &L)
{
int i,n;
cin>>n; //输入的值不大于 MAXSIZE
for(i=1;i<=n;i++)
{
cin>>L.r[i].key;
L.length++;
}
}
void show(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
if(i==1)
cout<<L.r[i].key;
else
cout<<" "<<L.r[i].key;
}
void Merge(RedType R[],RedType T[],int low,int mid,int high)
{
int i,j,k;
i=low; j=mid+1;k=low;
while(2分)
{
if(2分) T[k++]=R[i++];
else T[k++]=R[j++];
}
while(2分)
T[k++]=R[i++];
while(2分)
T[k++]=R[j++];
}
void MSort(RedType R[],RedType T[],int low,int high)
{
int mid;
RedType *S=new RedType[MAXSIZE];
if(low==high)2分;
else
{
mid=(low+high)/2;
2分;
2分;
Merge(S,T,low,mid,high);
}
}
void MergeSort(SqList &L)
{
MSort(L.r,L.r,1,L.length);
}
int main()
{
SqList R;
R.r=new RedType[MAXSIZE+1];
R.length=0;
Create_Sq(R);
MergeSort(R);
show(R);
return 0;
}
第一行输入一个数n(输入的值不大于 MAXSIZE)，接下来输入n个数。
7
24 53 45 45 12 24 90
输出排序结果。
12 24 24 45 45 53 90
相邻两个有序子序列的归并。
#include <iostream>
#define MAXSIZE 1000
using namespace std;
typedef struct
{
int key;
char *otherinfo;
}RedType;
void Create_Sq(RedType *R)
{
int i,n;
cin>>n; //输入个数
for(i=0;i<n;i++)
cin>>R[i].key;
}
void Merge(RedType R[],RedType T[],int low,int mid,int high)
{
int i,j,k;
i=low; j=mid+1;k=low;
while(2分)
{
if(2分) T[k++]=R[i++];
else T[k++]=R[j++];
}
while(2分)
T[k++]=R[i++];
while(2分)
T[k++]=R[j++];
}
void show(RedType *T,int low,int high)
{
int i;
for(i=low;i<=high;i++)
if(i==low)
cout<<T[i].key;
else
cout<<" "<<T[i].key;
}
int main()
{
RedType *R=new RedType[MAXSIZE];
RedType *T=new RedType[MAXSIZE];
Create_Sq(R);
int low,mid,high;
cin>>low>>mid>>high;
Merge(R,T,low,mid,high);
show(T,low,high);
return 0;
}
第一行输入一个数n，第二行输入n个数，第三行输入3个数L、M、H，表示将L至M的有序子序列与M＋1至H的有序子序列进行归并操作。
7
24 45 45 53 12 24 90
0 3 6
输出归并后的结果。
12 24 24 45 45 53 90
基数排序。
#include <iostream>
#define MAXNUM_KEY 8 //关键字项数的最大值
#define RADIX 10 //关键字基数，此时是十进制整数的基数
#define MAX_SPACE 10000
using namespace std;
typedef struct
{
char keys[MAXNUM_KEY]; //关键字
int next;
}SLCell;
typedef struct
{
SLCell r[MAX_SPACE]; //静态链表的可利用空间，r[0]为头结点
int keynum; //记录的当前关键字个数
int recnum; //静态链表的当前长度
}SLList; //静态链表类型
void InitList(SLList *L)
{
int i,n,keynum;
cin>>n>>keynum;
(*L).keynum=keynum;
(*L).recnum=n;
for(i=1;i<=n;i++)
cin>>(*L).r[i].keys;
}
void Distribute(SLCell *r,int i,int *f,int *e)
{
int j,p;
for(j=0;j<RADIX;++j) f[j]=0;
for(p=r[0].next;p;p=r[p].next)
{
j=r[p].keys[i]-'0';
if(!f[j])
2分=p;
else
r[e[j]].next=p;
2分=p;
}
}
void Collect (SLCell *r,int i,int *f,int *e)
{
int j,t;
for(j=0;!f[j];j++);
r[0].next=2分;
t=2分;
while(j<RADIX-1)
{
for(j++;j<RADIX-1&&!f[j];j++) ;
if(f[j])
{
2分=f[j];
2分=e[j];
}
}
r[t].next=0;
}
void RadixSort(SLList &L)
{
int i;
int f[RADIX],e[RADIX];
for(i=0;i<L.recnum;++i) L.r[i].next=i+1;
L.r[L.recnum].next = 0;
for(i=L.keynum-1;i>=0;i--)
{
Distribute(L.r,i,f,e);
Collect(L.r,i,f,e);
}
}
void print(SLList L)
{
int p,flag=1;
for(p=L.r[0].next;p;p=L.r[p].next)
{if(flag)
{cout<<L.r[p].keys;flag=0;}
else
cout<<" "<<L.r[p].keys;
}
}
int main()
{
SLList l;
InitList(&l);
RadixSort(l);
print(l);
return 0;
}
第一行输入待排序个数n和关键字个数keynum，接下来输入n个数（字符串）。
10 3
278 109 063 930 589 184 505 269 008 083
输出排序结果。
008 063 083 109 184 269 278 505 589 930
本函数的功能是从有N个元素的线性表A中查找第K大的元素。函数的初始调用为Qselect(A, K, 0, N-1)。请完成下列填空。
ElementType Qselect( ElementType A[], int K, int Left, int Right )
{
ElementType Pivot = A[Left];
int L = Left, R = Right+1;
while (1) {
while ( A[++L] > Pivot ) ;
2分;
if ( L < R ) Swap( &A[L], &A[R] );
else break;
}
Swap( &A[Left], &A[R] );
if ( K < (L-Left) )
return Qselect(A, K, Left, R-1);
else if ( K > (L-Left) )
2分;
else
return Pivot;
}